package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/17 15:01
 *
 构建乘积数组：b数组的元素为a中（除第i个元素外）的乘积

[1,2,3,4,5]
[120,60,40,30,24]
 */

import java.util.Arrays;

public class Main34 {
    //使用除法----要考虑0的情况
        public int[] multiply(int[] A) {
            if(A==null||A.length==0)return null;
            int cnt0=0,loc=0,mul0=1;
            int b[]=new int[A.length];
            for(int i=0;i<A.length;++i){
                if(A[i]==0){
                    cnt0++;
                    loc=i;
                    continue;
                }
                mul0*=A[i];
            }

            if(cnt0==1){
                b[loc]=mul0;
            }else if(cnt0>1){
                return b;
            }else {
                for(int i=0;i<A.length;++i){
                    b[i]=mul0/A[i];
                }
            }

            return b;
        }


        //不使用除法
        public int[] multiply2(int[] A) {
            if(A==null||A.length==0)return null;
            int len=A.length;
            int b[]=new int[len];
            //System.out.println(len);
            //赋值
            Arrays.fill(b,1);
            for(int i=0;i<len;++i){
                for(int j=0;j<len;++j){
                    if(i==j)continue;
                    b[i]*=A[j];
                }
            }
            return b;
        }

    //改善O(n^2)复杂度:上下三角，两次遍历
    //对于半三角来说，当前b的值为以前的累乘乘积
    public int[] multiply3(int[] A) {
        if(A==null||A.length==0)return null;
        int len=A.length;
        int b[]=new int[len];
        int down=1,up=1;
        for(int i=0;i<len;++i){
            b[i]=down;
            //System.out.println(b[i]+" down:"+down);
            down*=A[i];
        }
        for(int i=len-1;i>=0;--i){
            b[i]*=up;
            up*=A[i];
        }

        return b;
    }

    public static void main(String[] args) {
            int arr[]={1,2,3,4,5};
        int b[]=new Main34().multiply3(arr);
        for(int i:b){
            System.out.println(i);
        }

    }
}
